package visualizer.client.algorithms.rBst;

import visualizer.client.algorithms.AlgoResult;
import visualizer.client.algorithms.Algorithm;
import visualizer.client.bst.BNode;
import visualizer.client.bst.BinaryTree;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import static visualizer.client.utils.VisualizerUtils.DEFAULT_OUTER_COLOR;

/**
 * User: DDovzhenko
 * Date: 06.01.14
 * Time: 17:17
 */
public class RBSTAddingAlgorithm implements Algorithm {
    private BinaryTree tree;
    private List<AlgoResult> results = new ArrayList<AlgoResult>();
    boolean isAdded;

    @Override
    public AlgoResult performAlgorithmToStep(BinaryTree tree, int step, int inputValue) {
        return results.get(step);
    }

    @Override
    public int getStepsCount(BinaryTree binaryTree, int inputValue) {
        results.clear();
        isAdded = false;
        results.add(new AlgoResult(binaryTree.copyTree(false), " Вставка узла с ключом " + inputValue + ". Выполняем с вероятностью 1/(n+1) (n — размер дерева до вставки) вставку в корень, а с вероятностью 1 - 1/(n+1) — рекурсивную вставку в правое или левое поддерево в зависимости от значения ключа. Вероятность вставки в корень определяется генератором случайных чисел языка Java."));
        tree = binaryTree.copyTree(false);
        tree.refreshSizes();
        tree.setRootNode(insert(tree.getRoot(), createNewNode(inputValue)));
        results.add(new AlgoResult(tree, isAdded ? "Новый узел успешно добавлен" : "Узел с таким ключом уже существует и не может быть добавлен"));
        return results.size();
    }

    private BNode createNewNode(int inputValue) {
        BNode newNode = new BNode(inputValue);
        newNode.setInnerColor("lightgreen");
        newNode.setOuterColor("green");
        return newNode;
    }

    public BNode insert(BNode root, BNode newNode) {
        if (root == null) {
            results.add(new AlgoResult(tree.copyTree(true), "Здесь нет узла, поэтому создаем новый узел в этом месте"));
            isAdded = true;
            return newNode;
        }
        root.setOuterColor("red");
        if (root.getValue().equals(newNode.getValue())) {
            isAdded = false;
            return root;
        }
        int generatedNumber = new Random().nextInt(root.getSize() + 1);
        double probability = ((int)(1.0 / (root.getSize() + 1) * 10000)) / 100.0;
        results.add(new AlgoResult(tree.copyTree(true), "Вероятность вставки нового узла в корень текущего поддерева равна " + probability + "%."));
        if (generatedNumber == 0) {
            root.setInnerColor("lightblue");
            results.add(new AlgoResult(tree.copyTree(true), "Успех, выполним вставку нового узла в корень, на место выделенного узла. Сначала выполним обычную вставку и с помощью ротаций поднимем новый узел на свое место."));
            return insertAsRoot(root, newNode);
        }
        if (root.getValue() < newNode.getValue()) {
            results.add(new AlgoResult(tree.copyTree(true), "Неудача продолжаем искать место для нового узла. Сравниваем ключи в узлах: ключ " + newNode.getValue() + " больше ключа " + root.getValue() + ", обрабатываем правое поддерево"));
            setDefaultColorIfNotNull(root, root.getRightBNode());
            root.setRightBNode(insert(root.getRightBNode(), newNode));
        }
        if (root.getValue() > newNode.getValue()) {
            results.add(new AlgoResult(tree.copyTree(true), "Неудача, продолжаем искать место для нового узла. Сравниваем ключи в узлах: ключ " + newNode.getValue() + " меньше ключа " + root.getValue() + ", обрабатываем левое поддерево"));
            setDefaultColorIfNotNull(root, root.getLeftBNode());
            root.setLeftBNode(insert(root.getLeftBNode(), newNode));
        }
        tree.updateSize(root);
        return root;
    }

    public BNode insertAsRoot(BNode root, BNode newNode) {
        if (root == null) {
            results.add(new AlgoResult(tree.copyTree(true), "Здесь нет узла, поэтому создаем новый узел в этом месте"));
            isAdded = true;
            return newNode;
        }
        root.setOuterColor("red");
        if (newNode.getValue() < root.getValue()) {
            results.add(new AlgoResult(tree.copyTree(true), "Сравниваем ключи в узлах: ключ " + newNode.getValue() + " меньше ключа " + root.getValue() + ", обрабатываем левое поддерево"));
            setDefaultColorIfNotNull(root, root.getLeftBNode());
            root.setLeftBNode(insertAsRoot(root.getLeftBNode(), newNode));
            root.setOuterColor("red");
            results.add(new AlgoResult(tree.copyTree(true), "Выполняем ротацию вправо для узла с ключом " + root.getValue()));
            root = rotateRight(root);
            setDefaultColorIfNotNull(root.getRightBNode(), root);
        } else if (newNode.getValue() > root.getValue()) {
            results.add(new AlgoResult(tree.copyTree(true), "Сравниваем ключи в узлах: ключ " + newNode.getValue() + " больше ключа " + root.getValue() + ", обрабатываем правое поддерево"));
            setDefaultColorIfNotNull(root, root.getRightBNode());
            root.setRightBNode(insertAsRoot(root.getRightBNode(), newNode));
            root.setOuterColor("red");
            results.add(new AlgoResult(tree.copyTree(true), "Выполняем ротацию влево для узла с ключом " + root.getValue()));
            root = rotateLeft(root);
            setDefaultColorIfNotNull(root.getLeftBNode(), root);
        }
        return root;
    }

    private BNode rotateRight(BNode p) {
        if (p == null || p.getLeftBNode() == null) {
            return p;
        }
        BNode q = p.getLeftBNode();
        p.setLeftBNode(q.getRightBNode());
        q.setRightBNode(p);
        q.setSize(p.getSize());
        tree.updateSize(p);
        return q;
    }

    private BNode rotateLeft(BNode q) {
        if (q == null || q.getRightBNode() == null) {
            return q;
        }
        BNode p = q.getRightBNode();
        q.setRightBNode(p.getLeftBNode());
        p.setLeftBNode(q);
        p.setSize(q.getSize());
        tree.updateSize(q);
        return p;
    }

    private void setDefaultColorIfNotNull(BNode node, BNode checkNode) {
        if (checkNode != null) {
            node.setOuterColor(DEFAULT_OUTER_COLOR);
        }
    }
}
